package backtrack;
import java.util.*;
public class _13_51_N皇后 {
	List<List<String>> result = new ArrayList<>();
	List<String> item;
	char[][] arr;
    public List<List<String>> solveNQueens(int n) {
    	arr = new char[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = '.';
			}
		}    	
    	backtracking(n, 0);
    	return result;
    }
    public void backtracking(int n, int row) {
    	// row==n说明已经超过棋盘范围，此时的结果就是正确结果，进行存储
    	if(row == n) {
    		item = new ArrayList<>();
    		for(int i = 0; i < n; i++) {
    			String str = "";
    			for(int j = 0; j < n; j++) {
    				str += String.valueOf(arr[i][j]);
    			}
    			item.add(str);
    			System.out.println(str);
    		}
    		result.add(new ArrayList<>(item));
    		System.out.println();
    		return;
    	}
    	
    	for(int i = 0; i < n; i++) {
    		// 满足条件则放棋子
    		if(check(n, row, i)) {
    			arr[row][i] = 'Q';
    			backtracking(n, row + 1);
    			arr[row][i] = '.';
    		} 	
    	}
    	
    }
    public boolean check(int n, int row, int i) {
    	// 循环检查 行 列 左上 右上 所有是否有元素Q，有则不满足条件
    	// 不需要检查 左下 右下 因为是从前往后遍历的，这种遍历方式，我们还可以对行列的遍历进行剪枝操作
    	
    	// 行
    	for(int j = 0; j < n; j++) {
    		if(arr[row][j] == 'Q') {
    			return false;
    		}
    	}
    	// 列
    	for(int j = 0; j < n; j++) {
    		if(arr[j][i] == 'Q') {
    			return false;
    		}
    	}
    	
    	// 左上
    	for(int j = row - 1,k = i - 1; j >= 0 && k >= 0; j--,k--) {
    		if(arr[j][k] == 'Q') {
    			return false;
    		}
    	}
    	// 右上
    	for(int j = row - 1,k = i + 1; j >= 0 && k < n; j--,k++) {
    		if(arr[j][k] == 'Q') {
    			return false;
    		}
    	}
    		
    	// 所有条件都遍历完依旧没用触发不满足，则说明满足条件
    	return true;
    }
    public static void main(String[] args) {
    	new _13_51_N皇后().solveNQueens(4);
	}
}
